# coding=utf-8
class page:
    def __init__(self, num, time, freq=0):
        self.num = num
        self.time = time
        self.freq = freq  # 新增频率计数


class main:
    def __init__(self, a, size):
        self.M = size
        self.lv = 0
        self.ci = 0
        self.N = len(a)
        self.arr_int = a
        self.res = ""
        self.que = ""
        self.b = [page(-1, self.M - i - 1, 0) for i in range(0, self.M)]
        self.c = [[-1 for i in range(0, self.N)] for j in range(0, self.M)]
        self.queue = []
        self.k = -1
        self.flag = -1
        self.process()

    def get_res(self):
        return self.res

    # 获取最少使用频率的页面索引
    def get_min_freq(self, b):
        min_freq = float('inf')
        min_idx = 0
        for i in range(0, self.M):
            if b[i].freq < min_freq:
                min_freq = b[i].freq
                min_idx = i
            # 如果频率相同，选择在内存未使用的时间最长的
            elif b[i].freq == min_freq and b[i].time > b[min_idx].time:
                min_idx = i
        return min_idx

    def equation(self, fold, b):
        for i in range(0, self.M):
            if fold == b[i].num:
                return i
        return -1

    # 最少使用算法
    def lfu(self, fold, b):
        val = self.equation(fold, b)
        if val >= 0:
            # 页面已在内存中，增加其频率，但不需要更新时间
            # 只有在页面不在内存中并且需要调入时，才需要更新其他页面的时间，以便在替换时能够正确判断哪个页面是最久未使用的
            b[val].freq += 1
        else:
            # 页面不在内存中，需要调入
            self.queue.append(fold)
            self.k += 1
            # 内存未满  flag 为未满时的内存块存储索引
            if self.flag < self.M - 1:
                self.flag += 1
                b[self.flag].num = fold
                b[self.flag].freq = 1  # 新页面的频率为1
            # 内存已满，选择替换频率最低的页面
            else:
                idx = self.get_min_freq(b)
                b[idx].num = fold
                b[idx].freq = 1
                b[idx].time = 0  # 重置时间

            # 更新其他页面的时间 两种情况均要用 所以可以提取出来 但 LRU 不行 因为 val 的取值位置不同
            # 这里因为涉及到只有要进行页面置换时才会去修改 times 其余时间只是修改 freq 所以要添加 b[i].num != -1
            for i in range(0, self.M):
                if i != val and b[i].num != -1:
                    b[i].time += 1

    def Myprint(self, a):
        self.res = self.res + "|------"
        for j in range(0, self.N - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"
        for j in range(0, self.N):
            self.res = self.res + "|%5d" % (a[j]) + " "
        self.res = self.res + '|\n'
        self.res = self.res + "|------"
        for j in range(0, self.N - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"
        for i in range(0, self.M):
            for j in range(0, self.N):
                if self.c[i][j] == -1:
                    self.res = self.res + "|%5c" % (32) + " "
                else:
                    self.res = self.res + "|%5d" % (self.c[i][j]) + " "
            self.res = self.res + "|\n"
        self.res = self.res + "|------"
        for j in range(0, self.N - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"
        self.ci = self.k + 1
        self.lv = (float)((self.k + 1) / self.N)

    def print_que(self):
        self.que = ""
        for i in range(0, self.k + 1):
            self.que = self.que + "%d " % (self.queue[i])

    def process(self):
        a = self.arr_int
        self.b = [page(-1, self.M - i - 1, 0) for i in range(0, self.M)]
        self.c = [[-1 for i in range(0, self.N)] for j in range(0, self.M)]
        self.queue = []
        self.k = -1
        self.flag = -1
        for i in range(0, self.N):
            self.lfu(a[i], self.b)
            # self.c[0][i] = a[i]
            for j in range(0, self.M):
                self.c[j][i] = self.b[j].num
        self.Myprint(a)
        self.print_que()

    def get_lv(self):
        return self.lv

    def get_que(self):
        return self.que

    def get_ci(self):
        return self.ci


class LFU:
    def __init__(self, page_sequence, memory_size):
        """
        初始化LFU算法
        :param page_sequence: 页面访问序列
        :param memory_size: 内存块数
        """
        self.page_sequence = page_sequence
        self.memory_size = memory_size

    def run(self):
        """
        执行LFU算法
        :return: (缺页次数, 缺页率, 详细步骤)
        """
        memory = []  # 内存状态
        freq_count = {}  # 页面使用频率计数
        page_time = {}  # 页面进入时间
        fault_count = 0  # 缺页次数
        detailed_steps = []  # 详细步骤记录
        time_counter = 0  # 时间计数器

        for i, page in enumerate(self.page_sequence):
            time_counter += 1
            # 记录当前步骤前的内存状态
            current_memory = memory.copy()

            if page in memory:
                # 页面已在内存中，增加其使用频率
                freq_count[page] += 1
                removed_page = None
                page_fault = False
            else:
                # 页面不在内存中，缺页
                fault_count += 1

                if len(memory) >= self.memory_size:
                    # 内存已满，需要替换
                    # 查找使用频率最低的页面
                    min_freq = min(freq_count.values())
                    min_freq_pages = [p for p in memory if freq_count[p] == min_freq]

                    if len(min_freq_pages) == 1:
                        # 只有一个最低频率页面
                        removed_page = min_freq_pages[0]
                    else:
                        # 有多个最低频率页面，选择最早进入的
                        removed_page = min(min_freq_pages, key=lambda p: page_time[p])

                    memory.remove(removed_page)
                    # 从相应的字典中删除被替换页面的信息
                    del freq_count[removed_page]
                    del page_time[removed_page]
                else:
                    # 内存未满
                    removed_page = None

                # 添加新页面
                memory.append(page)
                freq_count[page] = 1
                page_time[page] = time_counter
                page_fault = True

            # 记录此步骤的详细信息
            step_info = {
                'step': i + 1,
                'page': page,
                'memory_before': current_memory,
                'memory_after': memory.copy(),
                'page_fault': page_fault,
                'removed_page': removed_page,
                'freq_count': freq_count.copy()
            }
            detailed_steps.append(step_info)

        # 计算缺页率
        fault_rate = (fault_count / len(self.page_sequence)) * 100

        return fault_count, fault_rate, detailed_steps


if __name__ == "__main__":
    test_sequence = [1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6]
    lfu = LFU(test_sequence, 3)
    fault_count, fault_rate, steps = lfu.run()
    print(f"缺页次数: {fault_count}, 缺页率: {fault_rate:.2f}%")

    # 测试 main 类
    m = main(test_sequence, 3)
    print(f"main类缺页率: {m.get_lv():.2f}, 缺页次数: {m.get_ci()}")